package com.bitauto.i.commonUtils.leet;

import java.util.HashMap;
import java.util.Map;

public class Answer5 {

    public static void main(String[] args) {
        String s="abacccdddcc";
        String result1=longestPalindrome1(s);
        System.out.println("result1:"+result1);

        String result2=longestPalindrome2(s);
        System.out.println("result2:"+result2);
    }

    private static String longestPalindrome1(String s) {
        String ans = "";
        int max = 0;
        int n=s.length();
        for (int i=0;i<n;i++){
            for (int j=i+1;j<=n;j++){
                String test = s.substring(i,j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        }
        return ans;
    }

    private static boolean isPalindromic(String test) {
        int len = test.length();
        for(int i=0;i<len/2;i++){
            if(test.charAt(i)!=test.charAt(len-i-1)){
                return false;
            }
        }
        return true;
    }

    private static String longestPalindrome2(String s) {
        if (s.equals("")){
            return "";
        }
        int n=s.length();
        String origin=s;
        //翻转
        String reverse=new StringBuffer(s).reverse().toString();
        int[][] arr = new int[n][n];
        int maxLen = 0;
        int maxEnd = 0;

        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if(origin.charAt(i)==reverse.charAt(j)){
                    if(i==0 || j==0){
                        arr[i][j]=1;
                    }else{
                        arr[i][j]=arr[i-1][j-1]+1;
                    }
                }

                if(arr[i][j]>maxLen){
                    int beforeRev=n-1-j;
                    //判断是否对应
                    if(beforeRev+arr[i][j]-1==i){
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }

            }
        }
        return s.substring(maxEnd-maxLen+1,maxEnd+1);
    }

    /**
     * 求两个字符串的最长公共子串
     *
     * @param str
     * @param str2
     * @return
     */
    /*public static int getLCSLength(String str, String str2){

    }*/


}
